import java.util.HashMap;
import java.util.Map;

public class Test {
    public static void main(String[] args) {
        //
        String strss = "ADOBECODEBANC";
        String strtt = "ABC";
        Solution solution = new Solution();
        String res = solution.minWindow(strss,strtt);
        System.out.println(res);
    }
}

class Solution {
    //方法三——用hash
    public String minWindow(String ss, String tt) {
        //换成字符数组
        char[]  s = ss.toCharArray();
        char[]  t = tt.toCharArray();

        Map<Character, Integer> map1 = new HashMap<>();//字符，出现的次数
        Map<Character, Integer> map2 = new HashMap<>();
        for(char c : t) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }

        int begin = -1,minLen = Integer.MAX_VALUE;
        int flag2 = -1;
        for(int left = 0,right = 0; right < s.length; right++){
            //进窗口——哈希表2
            map2.put(s[right], map2.getOrDefault(s[right], 0) + 1);

            //判断
            int flag = -1;
            for(Map.Entry<Character, Integer> entry : map1.entrySet()){

                //这样“遍历”判断
                char key = entry.getKey();
                int value = entry.getValue();

                if(map2.containsKey(key)&&map2.get(key)>=value){
                    continue;
                }else{
                    flag = 1;
                    break;
                }

            }
            //更新结果
            while(flag==-1){
                if(right - left + 1 < minLen){
                    minLen = right - left + 1;
                    begin = left;
                    //flag = 1;
                }

                //出窗口
                char out = s[left];
                if(map1.containsKey(out)&&map1.get(out)>=map2.get(out)){
                    //flag2 = 1;
                    break;
                }
                //if(flag2==1){//先在要出窗口的这个元素出窗口后，窗口内容就不符合要求了——现在left是临界值
                //   break;
                //}
                map2.put(s[left], map2.get(s[left]) - 1);
                left++;

            }


        }

        if(begin == -1){
            return "";
        }

        String res = ss.substring(begin,begin+minLen);
        return res;

    }
    //方法二——听完老师讲的第四步（代码编写）
    public String minWindow2(String ss, String tt) {
        char[] s = ss.toCharArray();//字符串 转化成 字符数组，方便使用
        char[] t = tt.toCharArray();

        int[] hash1 = new int[200];//统计tt中字符出现的频次
        int kinds = 0;//统计tt中字符的种类数
        for(char c : t) {
            if(hash1[c] == 0) kinds++;
            hash1[c]++;
        }
        int[] hash2 = new int[200];//存储窗口中字符出现的频次

        String res;//返回


        int begin = -1,minLen = Integer.MAX_VALUE;//也可以写的近一点（用在哪里）
        for(int left = 0,right = 0,count = 0; right < s.length; right++){//有关变量，哪里用，哪里写（一点小感悟~）
            //进窗口
            int in = s[right];//清楚
            hash2[in]++;
            if(hash1[in]==hash2[in]) count++;//维护count（count：窗口中有效字符的种类数——这里的“有效”，比较“严格”，需要数目也对上）


            //判断
            while(count==kinds){
                //更新结果（这里别着急，最后一次while的时候，肯定是当次right对应的正确结果）——不知道维护的是什么变量？看你要维护什么呀？？？不要钻牛角尖想老师怎么做的，可以根据目的进行推敲一下呀~~
                if(minLen>=right - left + 1){
                    minLen = right - left + 1;
                    begin = left;
                }


                //出窗口
                char out = s[left];
                if(hash1[out]==hash2[out]) count--;
                hash2[out]--;
                left++;
            }



        }
        if(begin == -1) return "";
        return ss.substring(begin,begin+minLen);

    }
    //方法一：听完老师讲的前两步
    public String minWindow1(String ss, String tt) {

        String res = "";//返回
        int ret = -1;
        int retlen = ss.length();

        int left = 0, right = 0;
        int count = 0;
        int len = tt.length();

        char[] t = tt.toCharArray();//方便操作
        char[] s = ss.toCharArray();

        int[] hash1 = new int[60];
        int[] hash2 = new int[60];
        for(char ch:t){
            int index = ch - 'A';
            hash1[index]++;
        }

        for(right= 0; right < s.length; right++){
            //进窗口
            int in = s[right] - 'A';
            hash2[in]++;
            if(hash2[in] <= hash1[in]){
                count++;
            }

            //判断
            while(count==len){
                //更新结果（我咋感觉，这个在出窗口之后也能行，而且更好？？？）
                //res = ss.substring(left,right+1);
                //ret = left;

                //出窗口
                int out = s[left] - 'A';

                if(hash2[out] <= hash1[out]){
                    count--;
                    //更新结果
                    int len2 = right - left +1;
                    if(len2<=retlen){
                        retlen = len2;
                        ret = left;

                    }


                }
                left++;
                hash2[out]--;
            }

        }
        if(ret!=-1){
            res = ss.substring(ret , ret+retlen);
        }


        return res;

    }
}